package first_practice;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-230-二叉搜索树中第 K 小的元素
 * @date 2025/4/13 16:55
 */
public class Solution230 {
    public int kthSmallest(TreeNode root, int k) {
        // 中序遍历二叉搜索树即可
        // 不需要遍历整个树，只需要遍历到第k个节点就行
        Deque<TreeNode> stack = new LinkedList<>();

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            k--;
            if (k == 0) break;
            root = root.right;
        }

        return root.val;
    }
}
